package org.example.day02;

import java.util.*;

/**
 * @author zlxad
 * @version 1.0
 * @description: TODO +
 * <div>  在某个项目中有多个任务（用 tasks 数组表示）需要您进行处理，其中 tasks[i] = [s<sub>i</sub>, e<sub>i</sub>]，你可以在 s<sub>i</sub> &lt;= day &lt;= e<sub>i</sub> 中的任意一天处理该任务。请返回你可以处理的最大任务数。 </div> <div>  注：一天可以完成一个任务的处理。 </div>
 *
 * 在某个项目中有多个任务（用 tasks 数组表示）需要您进行处理，其中 tasks[i] = [si, ei]，
 * 你可以在 si <= day <= ei 中的任意一天处理该任务。请返回你可以处理的最大任务数。
 * 注：一天可以完成一个任务的处理。
 * @date 2024/3/11 15:22
 */
//可能时间复杂度较高,大家可以优化一下

class Task {
    int start, end; // 定义任务的开始时间和结束时间
    Task(int start, int end) { // 构造函数
        this.start = start;
        this.end = end;
    }
}

public class test034 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); // 创建扫描器读取输入数据
        int n = scanner.nextInt(); // 读取任务数量n
        List<Task> tasks = new ArrayList<>(); // 创建任务列表存储所有任务
        for(int i = 0; i < n; i++) { // 遍历n个任务
            int s = scanner.nextInt(), e = scanner.nextInt(); // 读取每个任务的开始时间和结束时间
            tasks.add(new Task(s, e)); // 将任务添加到任务列表中
        }

        // 按任务的开始时间对任务进行排序
        Collections.sort(tasks, Comparator.comparingInt(a -> a.start));

        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 创建一个优先队列，用来存储任务的结束时间，确保优先处理早结束的任务
        int maxTasks = 0; // 初始化可以处理的最大任务数

        for(int currentDay = 1; currentDay <= 100000; currentDay++) { // 从第1天开始到最后一天遍历每一天

            for(int i = 0; i < tasks.size() && tasks.get(i).start <= currentDay; i++) { // 遍历所有任务，找出今天可以开始的任务
                pq.offer(tasks.get(i).end); // 将可以开始的任务的结束时间加入优先队列
                tasks.remove(i); // 从任务列表中移除这个任务，因为它已经被加入到了优先队列中
                i--; // 因为移除了一个元素，所以索引要减1，以免跳过下一个任务
            }

            while(!pq.isEmpty() && pq.peek() < currentDay) { // 清除所有已经过期的任务（即当前日期已经超过了任务的结束日期）
                pq.poll(); // 从优先队列中移除过期的任务
            }

            if(!pq.isEmpty()) { // 如果优先队列不为空，说明有任务可以在今天完成
                pq.poll(); // 移除一个任务（即完成这个任务）
                maxTasks++; // 完成任务数加1
            }
        }

        System.out.println(maxTasks); // 输出可以完成的最大任务数
        scanner.close(); // 关闭扫描器
    }
}

